class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
      sort(nums.begin(),nums.end());
      int sum = 0;
      int index = 0;
      for(int i = 0;i < nums.size() && k > 0;i++){
        if(nums[i] < 0){
          nums[i] *= -1;
          k--;
        }
        if(nums[i] == 0){
          index = 1;
        }
      }
      sort(nums.begin(),nums.end());
      if(k % 2 != 0 && index == 0){
        nums[0] *= -1;
      }
      for(int a : nums){
        sum += a;
      }
    return sum;
   }
};
